package com.hy.Three394;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;

/**
 * Created With IntelliJ IDEA.
 * Descriptions:100276. 最短路径中的边
 *
 * 给你一个 n 个节点的无向带权图，节点编号为 0 到 n - 1 。图中总共有 m 条边，用二维数组 edges 表示，
 * 其中 edges[i] = [ai, bi, wi] 表示节点 ai 和 bi 之间有一条边权为 wi 的边。
 *
 * 对于节点 0 为出发点，节点 n - 1 为结束点的所有最短路，你需要返回一个长度为 m 的 boolean 数组 answer ，
 * 如果 edges[i] 至少 在其中一条最短路上，那么 answer[i] 为 true ，否则 answer[i] 为 false 。
 * 请你返回数组 answer 。
 *
 * 注意，图可能不连通。
 * 示例 1：
 * 输入：n = 6, edges = [[0,1,4],[0,2,1],[1,3,2],[1,4,3],[1,5,1],[2,3,1],[3,5,3],[4,5,2]]
 * 输出：[true,true,true,false,true,true,true,false]
 * 解释：以下为节点 0 出发到达节点 5 的 所有 最短路：
 * 路径 0 -> 1 -> 5 ：边权和为 4 + 1 = 5 。
 * 路径 0 -> 2 -> 3 -> 5 ：边权和为 1 + 1 + 3 = 5 。
 * 路径 0 -> 2 -> 3 -> 1 -> 5 ：边权和为 1 + 1 + 2 + 1 = 5 。
 *
 * User:Mr.Du
 * Date:2024/4/21
 * Time:13:07
 */
public class FindAnswer {

    public boolean[] findAnswer(int n, int[][] edges) {
        boolean[] ans = new boolean[edges.length];
        List<int[]>[] list = new List[n];
        Arrays.setAll(list, e -> new ArrayList<>());
        for(int[] edge : edges){
            int x = edge[0], y = edge[1], z = edge[2];
            list[x].add(new int[]{y, z});
            list[y].add(new int[]{x, z});
        }
        int[] d1 = new int[n];
        int[] d2 = new int[n];
        dijkstra(d1, 0, list);
        dijkstra(d2, n - 1, list);
        int d = d1[n - 1];
        for(int i = 0; i < edges.length; i++){
            int x = edges[i][0], y = edges[i][1], z = edges[i][2];
            if(d1[x] + d2[y] + z == d ||  d1[y] + d2[x] + z == d){
                ans[i] = true;
            }
        }

        return ans;
    }

    public void dijkstra(int[] d, int s, List<int[]>[] list){
        Arrays.fill(d, Integer.MAX_VALUE);
        d[s] = 0;
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        pq.offer(new int[]{0, s});
        while(!pq.isEmpty()){
            int[] cur = pq.poll();
            int dist = cur[0];
            int i = cur[1];
            if(dist > d[i]) continue;
            for(int[] edge : list[i]){
                int b = edge[0];
                int weight = edge[1];
                int nd = d[i] + weight;
                if(d[b] > nd){
                    d[b] = nd;
                    pq.offer(new int[]{d[b], b});
                }
            }
        }
    }
}
